package od.one;

/**
 * @author: Shelly
 * @create: 2024-01-30 15:00:15
 * @version: 1.0
 * @describe: 转盘寿司
 * 题目描述
 * 寿司店周年庆，正在举办优惠活动回馈新老客户。
 * 寿司转盘上总共有 n 盘寿司，prices[i] 是第i盘寿司的价格，
 * 如果客户选择了第i盘寿司，寿司店免费赠送客户距离第 i 盘寿司最近的下一盘寿司j，前提是 prices[j]<prices[i]，如果没有满足条件的j，则不赠送寿司。
 * 每个价格的寿司都可无限供应。
 * 输入描述
 * 输入的每一个数字代表每盘寿司的价格，每盘寿司的价格之间使用空格分隔，例如：
 * 表示：
 * · 第0 盘寿司价格 prices[0]为3
 * · 第1 盘寿司价格 prices[1]为 15
 * · 第2 盘寿司价格 prices[2]为6
 * · 第3 盘寿司价格prices[3]为 14
 * · 寿司的盘数n范围为: 1≤n≤500
 * 每盘寿司的价格price 范围为: 1≤ price≤ 1000
 * 输出描述
 * 输出享受优惠后的一组数据，每个值表示客户选择第i 盘寿司时实际得到的寿司的总价格。使用空格进行分隔，例如：
 *
 * 输入 315614
 * 输出 321917
 *
 * 用例解析
 * 根据题目的描述，客户选择了第i盘寿司，寿司店免费赠送距离第i盘寿司最近的下一盘寿司j，且 prices[j]< prices[i]。如果没有满足条件的j，则不赠送寿司。因此，对于每一盘寿司，我们需要找到其价格右侧第一个比它小的寿司的价格，并将其加到当前寿司的价格上。
 * 给定输入 3 15 6 14 , 我们来逐个分析:
 * 1.第0盘寿司价格为3，没有比它更小的价格，所以输出为 3。
 * 2.第1 盘寿司价格为 15，它右侧最近的更小价格是 6 (第2 盘寿司) ，所以输出为1
 * 3.第2 盘寿司价格为6，它右侧最近的更小价格是3 (第0 盘寿司) ，所以 输出为 9。
 * 4.第3盘寿司价格为 14，它右侧最近的更小价格是3 (第0盘寿司) ，所以输出为 17。
 * 综合以上, 输出结果为 3 21 9 17。
 * 通过这个用例，可以得出数组是可以循环到头部继续寻找
 */
public class OD13 {
}
/*
* 解题思路
优惠规则是每个寿司盘可以用它右边第一个比它便宜的寿司盘的价格来享受优惠。如果右边没有更便宜的寿司盘，则保持原价。寿司盘是循环的，即最后一个寿司盘的右边是第一个寿司盘。
解题思路如下：
1.数据处理：将读取的字符串按空格分割，转换成整数数组 prices ，这个数组包含了所有寿司盘的价格。同时，获取数组的长度n，代表寿司盘的总数。
2.初始化数据结构：创建一个与价格数组等长的结果数组 res来存储每个寿司盘享受优惠后的价格，并初始化一个双端队列 stack 作为栈，用来跟踪价格的索引。
3.遍历价格数组：由于寿司盘是循环的，需要遍历2 * n - 1 次来确保每个寿司盘都能找到它右边的第一个更便宜的寿司盘。使用模运算来处理循环数组的索引。
4.处理栈：在遍历过程中，对于每个价格，检查栈顶元素(即之前遍历过的价格) 是否大于当前价格。如果是，则说明找到了一个更便宜的寿司盘，计算栈顶元素对应寿司盘的优惠价格并更新到结果数组 res中，然后将该元素出栈。重复此过程直到栈为空或栈顶元素小于当前价格。第一轮遍历 (即j < n时) 将每个索引加入栈中。
5.处理剩余元素：遍历结束后，栈中可能还有元素，这些元素代表它们右侧没有更小的价格，因此直接将它们的价格作为结果。
整个解题思路利用了栈这一数据结构来有效地跟踪和更新每个寿司盘的优惠价格，通过一次遍历来优化算法的时间复杂度。
*
* */